#include <string>
using std::string;
class Solution {
public:
    enum { N = 25 };
    bool dp[N][N];
    // 初始化的时候要注意如果奇数位置一直是*，那dp[0][i + 1]就一直可以是true
    // dp[i][j]：
    // 当p[j - 1] == ‘*’的时候，考虑两种情况
    // p[j - 2] == '.': dp[i][j] = dp[i][j - 2] | dp[i - 1][j - 2] | dp[i -2][j - 2] | ...
    // p[j -2] != '.' : dp[i][j] = dp[i][j - 2] | dp[i - 1][j] && p[j - 2] == s[j - 1]
    bool isMatch(string s, string p) {
        //dp[i][j]表示s中的前i个数和p中的前j个数是否匹配
        dp[0][0] = true;
        for(int i = 1; i < p.size(); i+=2)
        {
        //    cout << p[i] << endl;
            if('*' != p[i]) break;
            dp[0][i + 1] = true;
        }
        // cout << dp[2][4] << ' ' << dp[1][4] << ' ' << dp[0][4] << endl;
        for(int i = 1; i <= s.size(); ++i)
            for(int j = 1; j <= p.size(); ++j)
            {
                if(p[j - 1] == '.' || p[j - 1] == s[i - 1])
                    dp[i][j] = dp[i - 1][j - 1];
                else if(p[j - 1] == '*')
                    dp[i][j] = dp[i][j - 2] || dp[i - 1][j] && (p[j - 2] == '.' || s[i - 1] == p[j -2]);
            }
        return dp[s.size()][p.size()];
    }
};